105. 从前序与中序遍历序列构造二叉树

Similar Question

leading to the advanced question

Solution Tips

方案一: 递归

var buildTree = function(preorder, inorder) {
    // 根据前序遍历和中序遍历确定二叉树, 其实简单来说就要确定 左中右节点的位置
    // 先拿最左侧的子树来参考一下思路
    // 前序遍历: 中左右
    // 中序遍历: 左中右

    // 最关键的一点就是, 中节点的左边是其左子树的遍历结果, 中节点的右边是其右子树的遍历结果
    if (!preorder.length || !inorder.length) return null;

    const preorderRoot = preorder[0];
	// TODO: 每次都 indexOf 太慢了, 可以建立一个哈希表, 下次快速查找到
    const inorderRootIndex = inorder.indexOf(preorderRoot);
    const leftSubTreeCount = inorderRootIndex;

    const node = new TreeNode(preorderRoot);
    // 递归的构造左子节点
    node.left = buildTree(preorder.slice(1, 1 + leftSubTreeCount), inorder.slice(0, inorderRootIndex));
    // 递归的构造右子节点
    node.right = buildTree(preorder.slice(1 + leftSubTreeCount), inorder.slice(inorderRootIndex + 1))

    return node;
};

方案二: 迭代解法

有点复杂, 看不懂

Loading Question... - 力扣（LeetCode）